import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ghp
 * @title 三数之和
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先对数据进行排序（升序），方便后续的逻辑处理
        Arrays.sort(nums);
        // 遍历nums，寻找出所有符合条件的元素组合，并且没有重复的组合
        List<List<Integer>> ans = new ArrayList<>(10);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                // 由于数组是升序排序的，当前值大于0，则后面的值一定大于0
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                // 去除重复的值，防止组合重复
                continue;
            }
            int l = i + 1; // 左指针，从前往后遍历nums
            int r = nums.length - 1; // 右指针，从后往前遍历nums
            // 利用双指针寻找出符合题意的三个元素
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) {
                    // 三数之和小于0，移动左指针（增），注意要去重，防止出现重复组合
                    while (l < r && nums[l] == nums[++l]) ;
                } else if (sum > 0) {
                    // 三数之和大于0，移动左指针（减），注意要去重，防止出现重复组合
                    while (l < r && nums[r] == nums[--r]) ;
                } else {
                    // 三数之和等于0，符合条件，则需要同时移动左右指针，并去重
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[r])));
                    while(l < r && nums[l] == nums [++l]);
                    while (l < r && nums[r] == nums[--r]) ;
                }
            }
        }
        return ans;
    }

}